package com.gitee.ywj1352.leecode;

/**
 * @author wenjie.yang on 2019/8/26.
 */
public class KPM {

    public int kpm(String target ,String pattern){

        char[] tchars = target.toCharArray();
        char[] pchars = pattern.toCharArray();

        //搜索的角标
        int i = 0 ;
        //匹配的角标
        int j = 0 ;

        int[] next =  getNext(pattern);

        while(i<tchars.length && j < pchars.length){
            if(j == -1 || tchars[i] == pchars[j]){
                //角标单个 匹配成功 就++
                j++;
                i++;
            }else{
                //移动到 next 的位置
                j = next[j];
            }
        }

        if (j == pattern.length()){
            return i-j;
        }
        return -1;
    }

    //next 函数就是 自匹配 ABCDABD
    //自匹配 当出现 相同的就 自匹配选择词条 出现的次数
    public int[] getNext(String pattern){
        char[] p = pattern.toCharArray();
        int[] next = new int[p.length];
        // 第一位设为-1，方便判断当前位置是否为搜索词的最开始
        next[0] = -1;
        int i = 0;
        int j = -1;

        while(i < p.length - 1) {
            if (j == -1 || p[i] == p[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                //不停的 让 模式串 回到原点 查看到底 出现过几次
                j = next[j];
            }
        }
        return next;
    }


    public static void main(String[] args) {
        KPM kpm = new KPM();
        int kpm1 = kpm.kpm("BBC ABCDAB ABCDABCDABDE", "ABCDABD");
        System.out.println(kpm1);
    }




}
